Digital communications networks have existed for over thirty years, for example, in wired and packet radio formats. One of the first packet radio network designs, called Alohanet, included a set of nodes that communicated with other members of the network via a set of relay, or base stations.
In wired computer networks, Ethernet-based systems include features designed to avoid message transmission conflicts. Computers on a single, Ethernet-based interconnection wire can independently send packets, or bursts, of information among themselves on the same wire, by multiplexing those transmissions in time. This “listen-before-talk” technique is called Carrier Sense Multiple Access with Collision Detection (CSMA-CD). An analogous communication system appears in Citizen's band radio, for example, through which one listens before transmitting, thus providing an ad hoc way for two or more stations in a network to share a particular frequency channel.
As networks of greater density appeared, it became desirable to segregate network nodes into smaller groups interconnected by special processors that relayed data between network segments. These processors are generally called routers, and are usually implemented as special purpose machines that perform few additional functions. For example, routers are not commonly used for user tasks such as mail or word processing or sensing. Router-based systems scale well, and are the basis for the Internet.
More recently, interest in ad hoc networks has emerged. An ad hoc network lacks a predefined topology; installation or setup of a node typically must be nearly automatic. Ad hoc networks can provide a large variety of services, for example, wireless LANs for computers.
Some communications networks, for example, mobile telephone networks, involve mobile units. A mobile telephone network includes portable devices that all communicate with a base station. Telephone calls are transmitted between the handset and the cell site to which it is currently closest. The cell relays the communications to the public telephone network, a private data network or directly to another phone in that same cell or another cell.
The cellular nature of the network is established by the planning of the cell antenna base station sites. The base stations are designed to be dense enough to permit the desired number of simultaneous communications links specified by the operator of the network.
In general, these networks suffer from similar problems. Whether via wire, as for a local area network, or via open geographic space, as for cellular telephony, the total communications traffic in the network initially increases with an increasing population of terminals; then the network saturates and further increases in active terminals do not result in increased total volume of communications, i.e., total throughput.
Thus, a typical cellular network has a limited capacity, in part due to sharing of radio frequencies by communications from multiple users. To a limited extent, multiple communications can take turns using a particular frequency in a particular geographic region, however a saturation level is typically reached as the number of communications attempting to use the same frequency increases. Thus, as a saturation level is reached, each user may be required to relinquish some usage of the communication frequency.
Newer network designs, which respond to this scaling problem, have demonstrated that scaling can be improved when the members of the network cooperatively engage in the communications. For example, in one approach, each node can be a data source or recipient, and all nodes can also act as relays or routers for information destined for other nodes. Each packet or message is decoded at each node that receives it, and that node then makes a decision whether to forward it to another node that will advance the packet closer to its destination.
This cooperative form of transport can localize communications and allows the same channels to be reused by multiple geographically distributed terminals or nodes. In a wired system, for example, routers can support such channel reuse. In both wired and radio communications systems, the notion that each member of the network is also a router, and thus relays information on behalf of other communicators, is embedded in the notion of ad hoc networks.
An advantage of this approach is that the decision process can be updated, for example, if the nodes are mobile and moving. A disadvantage arises because packets are typically decoded so that the forwarding node can examine the source and destination information and the number of “hops” the data has already made. The hop count is updated, the packet is re-coded for network transmission and the packet is passed onwards. Hence, the retransmitted packet is delayed by at least one packet transmission period plus whatever processing time is required for the decoding, encoding and forwarding decision.